package Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/5/9
 * \* Time: 12:17
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class Demo4 {

    public static void main(String[]args){
        //定义一个边界
        int border = -1;
        long[]arr = new long[100000];
        arr[0] = 1;
        arr[1] = 2;
        for(int i =2;i<100000;i++){
            long next = arr[i-1]+arr[i-2];
            if(border == -1 && next >= 1000000){
                border = i+1;
            }
            //由于只需保留最后6位，因此这里%1000000
            arr[i] = next % 1000000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            long f = arr[n-1];
            //如果n少于6位数的，直接输出，否则保留6位数字
            if(n < border){
                System.out.printf("%d\n",f);
            }else{
                System.out.printf("%06d\n",f);
            }

        }
    }


/*    public static void main2(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int a = 1;
            int b = 1;
            int c = 1;
            while(n > 2){
                c = a + b;
                a = b;
                b = c;
                --n;
            }
            int tmp = sum(c);
            System.out.println(tmp);
        }
    }
    public static int sum(int c){
        String str = c+"";
        int len = str.length();
        if(len < 6){
            return c;
        }
        StringBuilder sb = new StringBuilder();
        for (int i =str.length()-1;i>=str.length()-6;i--){
            sb.append(i);
        }
        sb.reverse();
        int n = Integer.parseInt(String.valueOf(sb));
        return n;
    }


    public static void main1(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int fy = sc.nextInt();
            int fm = sc.nextInt();
            int fd = sc.nextInt();
            int ly = sc.nextInt();
            int lm = sc.nextInt();
            int ld = sc.nextInt();
            int profit = profitOfYear(fy) - profitOfThisYear(fy, fm, fd - 1);
            profit += profitOfThisYear(ly,lm,ld);
            if(fy == ly) {
                profit -= profitOfYear(fy);
            }
            for(int i = fy+1;i<ly;i++) {
                profit += profitOfYear(i);
            }
            System.out.println(profit);
        }
    }
    //判断闰年
    public static boolean isLeapYear(int y){
        return (y % 400 == 0) || (y % 4 == 0 && y % 100 != 0);
    }
    //判断月份是否是素数
    public static int profitOfYear(int y){
        return 2 * 31
                + 1 * 28
                + 1 * 31
                + 2 * 30
                + 1 * 31
                + 2 * 30
                + 1 * 31
                + 2 * 31
                + 2 * 30
                + 2 * 31
                + 1 * 30
                + 2 * 31
                +(isLeapYear(y) ? 1:0);
    }
    //判断月份
    public static boolean isPrime(int m){
        return m == 2 || m == 3 || m == 5 || m == 7 || m == 11;
    }

    private static int profitOfThisYear(int year,int month,int day){
        int profit = 0;
        if(!isPrime(month)) {
            profit = day * 2;
        }else{
            profit = day;
        }

        while(--month>0) {
            switch(month) {
                case 1:case 8:case 10:case 12: profit += 62;
                    break;
                case 3:case 5:case 7: profit += 31;
                    break;
                case 4:case 6:case 9: profit += 60;
                    break;
                case 11: profit += 30;
                    break;
                default:
                    profit += (28+(isLeapYear(year)?1:0));
                    break;
            }
        }
        return profit;
    }*/




//    private static List<String> factorization(int a) {
//        List<String> ans = new ArrayList<>();
//        for(int i = 2; i<=Math.sqrt(a);i++){//i*i<=a,开根号
//            while(a%i == 0){
//                ans.add(String.valueOf(i));
//                a /= i;
//            }
//        }//10 = 2*5   21 = 3*7
//        if(a>1) {//走到最后a还是大于1 说明a是一个素数
//            ans.add(String.valueOf(a));
//        }
//        return ans;
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()) {
//            int a = sc.nextInt();
//            List<String> factors = factorization(a);
//            System.out.printf("%d = %s\n",a,String.join(" * ",factors));
//        }
//    }

//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            List<String> fac = getFac(n);
//            System.out.printf("%d = %s\n",n,String.join(" * ",fac) );
//        }
//    }
//
//    private static List<String> getFac(int n) {
//        List<String> ans = new ArrayList<>();
//        for (int i = 2;i<= Math.sqrt(n);i++){
//            while (n % i == 0){
//                ans.add(String.valueOf(i));
//                n /= i;
//            }
//
//        }
//        if(n > 1){
//            ans.add(String.valueOf(n));
//        }
//        return ans;
//    }

}
